package _mst;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 面试题 08.02. 迷路的机器人
 */
public class T0802 {
    private int[][] obstacleGrid;
    private List<List<Integer>> ans;

    public List<List<Integer>> pathWithObstacles(int[][] obstacleGrid) {
        this.obstacleGrid = obstacleGrid;
        ans = new ArrayList<>();
        dfs(obstacleGrid.length - 1, obstacleGrid[0].length - 1);
        Collections.reverse(ans);
        return ans;
    }

    private boolean dfs(int i, int j) {
        if (i < 0 || j < 0 || obstacleGrid[i][j] == 1) return false;
        ans.add(List.of(i, j));
        obstacleGrid[i][j] = 1;
        if ((i == 0 && j == 0) || dfs(i - 1, j) || dfs(i, j - 1)) return true;
        ans.remove(ans.size() - 1);
        return false;
    }
}
